Definition

#incomplete

Theorem

For any MAX SNP-hard problem, there does not exist a polynomial-time approximation scheme, unless P=NP.

References

  1. D. P. Williamson, D. B. Shmoys. Approximation Algorithms, Cambridge University Press, 2010, p. 14.
  2. https://en.wikipedia.org/wiki/SNP_(complexity)#MaxSNP